#pragma once

template <typename T>
class CLinkedList
{
private:
    struct Node
    {
        T m_data;
        Node* m_pPrev;
        Node* m_pNext;

        Node(Node* prev = nullptr, Node* next = nullptr)
            : m_pPrev(prev), m_pNext(next)
        {

        }

        Node(const T& data, Node* prev = nullptr, Node* next = nullptr)
            : m_data(data), m_pPrev(prev), m_pNext(next)
        {

        }
        Node(T&& data, Node* prev = nullptr, Node* next = nullptr)
            : m_data(std::move(data)), m_pPrev(prev), m_pNext(next)
        {

        }
    };

public:
    class iterator {
    public:
        iterator(Node* pElem)
        {
            m_pElem = pElem;
        }

        T& operator*()
        {
            return m_pElem->m_data;
        }

        iterator operator++()
        {
            return iterator{ m_pElem = m_pElem->m_pNext };
        }

        const iterator operator++(int)
        {
            iterator it{ m_pElem };
            m_pElem = m_pElem->m_pNext;
            return it;
        }

        bool operator!=(const iterator& other)
        {
            return m_pElem != other.m_pElem;
        }
    private:
        friend class CLinkedList;
        Node* GetNode() const
        {
            return m_pElem;
        }
        Node* m_pElem;
    };

    class const_iterator {
    public:
        const_iterator(Node* pElem)
        {
            m_pElem = pElem;
        }

        T& operator*()
        {
            return m_pElem->m_data;
        }

        const_iterator operator++()
        {
            return const_iterator{ m_pElem = m_pElem->m_pNext };
        }

        const const_iterator operator++(int)
        {
            const_iterator it{ m_pElem };
            m_pElem = m_pElem->m_pNext;
            return it;
        }

        bool operator!=(const const_iterator& other)
        {
            return m_pElem != other.m_pElem;
        }
    private:
        Node* m_pElem;
    };

    iterator begin()
    {
        return iterator{ front() };
    }
    iterator end()
    {
        return iterator{ m_pTail };
    }
    const_iterator begin() const
    {
        return const_iterator{ m_pHead->m_pNext };
    }
    const_iterator end() const
    {
        return const_iterator{ m_pTail };
    }

private:
    void Init()
    {
        m_pHead = new Node();
        m_pTail = new Node();
        m_pHead->m_pNext = m_pTail;
        m_pTail->m_pPrev = m_pHead;
        m_nSize = 0;
    }
public:
    CLinkedList()
    {
        Init();
    }
    CLinkedList(const CLinkedList& other)
    {
        Init();
        for (auto e : other) {
            PushBack(e);
        }
    }
    CLinkedList(CLinkedList&& other)
    {
        m_pHead = other.m_pHead;
        m_pTail = other.m_pTail;
        m_nSize = other.m_nSize;
        other.m_pHead = nullptr;
        other.m_pTail = nullptr;
    }
    CLinkedList(std::initializer_list<T> initList)
    {
        Init();
        for (auto e : initList)
        {
            PushBack(e);
        }
    }

    ~CLinkedList()
    {
        clear();
        delete m_pHead;
        delete m_pTail;
    }

    CLinkedList& operator=(const CLinkedList& other)
    {
        CLinkedList copy(other);
        std::swap(m_pHead, copy.m_pHead);
        std::swap(m_pTail, copy.m_pTail);
        std::swap(m_nSize, copy.m_nSize);
        return *this;
    }
    CLinkedList& operator=(CLinkedList&& other)
    {
        std::swap(m_pHead, other.m_pHead);
        std::swap(m_pTail, other.m_pTail);
        std::swap(m_nSize, other.m_nSize);
        return *this;
    }

    iterator front()
    {
        return m_pHead->m_pNext;
    }
    iterator back()
    {
        return m_pTail->m_pPrev;
    }

    iterator Insert(const iterator& itr, const T& e)
    {
        Node* pNode = itr.GetNode();
        Node* p = new Node(e, pNode, pNode->m_pNext);
        pNode->m_pNext->m_pPrev = p;
        pNode->m_pNext = p;
        m_nSize++;
        return p;
    }
    iterator Insert(const iterator& itr, T&& e)
    {
        Node* pNode = itr.GetNode();
        Node* p = new Node(std::move(e), pNode, pNode->m_pNext);
        pNode->m_pNext->m_pPrev = p;
        pNode->m_pNext = p;
        m_nSize++;
        return p;
    }
    iterator PushBack(const T& e)
    {
        return Insert(back(), e);
    }
    iterator PushBack(T&& e)
    {
        return Insert(back(), std::move(e));
    }
    iterator PushFront(const T& e)
    {
        return Insert(m_pHead, e);
    }
    iterator PushFront(T&& e)
    {
        return Insert(m_pHead, std::move(e));
    }

    void Earase(const iterator& it)
    {
        Node* pDel = it.GetNode();
        pDel->m_pNext->m_pPrev = pDel->m_pPrev;
        pDel->m_pPrev->m_pNext = pDel->m_pNext;
        delete pDel;
        m_nSize--;
    }
    void PopBack()
    {
        Earase(back());
    }
    void PopFront()
    {
        Earase(front());
    }

    int size() const
    {
        return m_nSize;
    }

    bool empty() const
    {
        return m_nSize == 0;
    }

    void clear()
    {
        Node* p = m_pHead->m_pNext;
        while ( p != m_pTail )
        {
            Node* pNext = p->m_pNext;
            delete p;
            p = pNext;
        }
        m_pHead->m_pNext = m_pTail;
        m_pTail->m_pPrev = m_pHead;
        m_nSize = 0;
    }

    void concat(const iterator& itr, const CLinkedList& other)
    {
        iterator it = itr;
        for (auto e : other)
        {
            it = Insert(it, e);
        }
    }

    void Show()
    {
        printf("size: %d\n", m_nSize);
        for (Node* p = m_pHead; p != nullptr; p = p->m_pNext)
        {
            printf("%p:%08x [%p][%p]\n", p, p->m_data, p->m_pPrev, p->m_pNext);
        }
        printf("\n");
        for (Node* p = m_pTail; p != nullptr; p = p->m_pPrev)
        {
            printf("%p:%08x [%p][%p]\n", p, p->m_data, p->m_pPrev, p->m_pNext);
        }
        printf("\n");
    }


private:
    Node* m_pHead;
    Node* m_pTail;
    int m_nSize;
};